【题解】[省选联考 2020 B 卷] 丁香之路

P6628原题链接

神仙题,抢个第一篇题解

题目大意:一条链上有 nn 个点,有 mm 条连接两个点的管道,所有管道必须钻一遍,求s到其他点的最短路

定义一条路径中,不走管道的那部分路径叫做自由路径。由于所有管道的长度和是固定的,那么我们要求的就是让自由路径长度最少

如果没有管道,路径肯定是从 sstt 的一条自由路径。假设现在有一条自由路径从 AABBA<BA<B),有一条管道从 CCDDC<DC<D),考虑以下几种情况:

  • A<C<B<DA<C<B<D,我们可以把路径变成ACDBA→C-D→B,最终的自由路径变成 AACCBBDDC<A<D<BC<A<D<B的情况同理。

  • A<C<D<BA<C<D<B,还是把路径变成ACDBA→C-D→B,最终的自由路径还是 AACCBBDD

  • A<B<C<DA<B<C<D,直接在 CDC-D 上加一条自由路径让它变成一个环(这里先不考虑图的连通性问题,一个环暂时可以认为是独立于其他部分存在的。连通性会在后面处理)

注意:因为是无向边,而且一条路径也可以翻转,所以方向并不重要

根据上面几种情况找规律,发现在原有的自由路径上加一条管道,相当于把管道那段区间反转。当然这只是找规律,实际上这样做是正确的,下面是证明:

可以发现每次添加管道并反转自由路径后,所有管道边和自由边维持了一个从 sstt 的欧拉路,因此这条路径一定可行。同时它一定是最短的,因为所有的自由边都没有交叉。

只不过剩下一个很严重的问题:上面所说的“欧拉路”不是真正意义上的欧拉路,因为这些路径可能还没连通呢,只是满足了欧拉路对点度数的需求。

想让这张图连通,需要把现有的已经连通的部分缩成一个点,然后在上面求最小生成树。易得让图连通需要的最小代价就是最小生成树长度和的两倍。

具体实现时,我们先处理所有管道,包括它们形成的连通块和需要的自由路径,然后枚举每个终点单独处理。求最小生成树的时候只需要加入所有必经的节点,而因为这张图中两点的距离就是数轴上距离,因此只需要加入相邻的必经点构成的边就一定能求出最小生成树。

时间复杂度O((m+n2)log)O((m+n^2)\log)log\log来自并查集和求 mst 时给边排序)。代码太丑了,就不放了。